K-means算法¶
K-means算法是集简单和经典于一身的基于距离的聚类算法,采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。
该算法认为类簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。
K-means通过迭代寻找k个类簇的一种划分方案，使得用这k个类簇的均值来代表相应各类样本时所得的总体误差最小。
k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能地分开。
k-means算法的基础是最小误差平方和准则,如果用数据表达式表示，假设簇划分为$\left(C_{1}, C_{2}, \ldots C_{k}\right)$，则我们的目标是最小化平方误差$E$: $$ E=\sum_{i=1}^{k} \sum_{x \in C_{i}}\left\|x-\mu_{i}\right\|_{2}^{2} $$
其中$\mu_{i}$是簇$C_i$的均值向量，有时也称质心，表达式为 $$ \mu_{i}=\frac{1}{\left|C_{i}\right|} \sum_{x \in C_{i}} x $$ 如果我们想直接寻求上式的最小值并不容易，这是一个NP难问题，只能采用启发式的迭代方法。
步骤¶
Step 1： 随机选取k个聚类质心点（cluster centroids）为$\mu_{1}, \mu_{2}, \ldots, \mu_{k} \in \mathbb{R}^{n}$。
Step 2：重复下面过程直到收敛
对于每一个样例$i$，计算其应该属于的类 $$ c^{(i)}:=\arg \min _{j}\left\|x^{(i)}-\mu_{j}\right\|^{2} $$
- Step 3:对于每一个类$j$，重新计算该类的质心 $$ \mu_{i}=\frac{1}{\left|C_{j}\right|} \sum_{x \in C_{j}} x $$
收敛指如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值，表示重新计算的质心的位置变化不大，趋于稳定.
参考资料
- ThomsonRen github https://github.com/ThomsonRen/mathmodels